package com.lw.leetcode.arr.c;

import com.lw.test.util.Utils;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 768. 最多能完成排序的块 II
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/13 10:35
 */
public class MaxChunksToSorted {


    public static void main(String[] args) {
        MaxChunksToSorted test = new MaxChunksToSorted();

        // 1
//        int[] arr = {5,4,3,2,1};

        // 4
//        int[] arr = {2, 1, 3, 4, 4};

        // 4
        int[] arr = Utils.getArr(2000, 1, 1);

        int i = test.maxChunksToSorted(arr);
        System.out.println(i);
    }

    public int maxChunksToSorted(int[] arr) {
        int length = arr.length;
        int[] items = new int[length];
        System.arraycopy(arr, 0, items, 0, length);
        Arrays.sort(items);
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = length - 1; i >= 0; i--) {
            map.computeIfAbsent(arr[i], v -> new ArrayList<>()).add(i);
        }
        int end = 0;
        int count = 0;
        for (int i = 0; i < length; i++) {
            int s = items[i];
            List<Integer> list = map.get(s);
            int index = list.get(list.size() - 1);
            list.remove(list.size() - 1);
            end = Math.max(end, index);
            if (end == i) {
                count++;
            }
        }
        return count;
    }

}
